package com.yun.algorithmproblem.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Leetcode1094 {
    /*
        思路：排序加小顶堆
        1.排序：使用sort方法
            可以重写compara方法
            也可以使用comparator.comparing方法，传入一个函数
        2.小顶堆
     */
    public boolean carPooling(int[][] trips, int capacity) {
        Arrays.sort(trips,Comparator.comparingInt(a->a[1]));//按照上车位置从小到大排列
        PriorityQueue<int[]> minHeap=new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));//小顶堆，按照下车位置从小到大排列，存储下车位置及下车人数。
        int cur=0;//当前车上人数
        for (int i = 0; i < trips.length; i++) {
            minHeap.offer(trips[i]);
            cur+=trips[i][0];
            while (minHeap.peek()[2]<=trips[i][1]){
                cur-=minHeap.poll()[0];
            }
            if(capacity<cur){
                return false;
            }
        }
        return true;
    }

    /*
        思路：差分数组

     */
    public boolean carPooling1(int[][] trips, int capacity){
        int toMax=0;
        for (int[] trip:trips){
            toMax=Math.max(toMax,trip[2]);
        }
        int[] diff=new int[toMax+1];
        for (int[] trip : trips) {
            diff[trip[1]]+=trip[0];
            diff[trip[2]]-=trip[0];
        }
        int count=0;
        for (int i = 0; i <=toMax; i++) {
            count+=diff[i];
            if(count>capacity){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] trip={{10,5,7},{10,3,4},{7,1,8},{6,3,4}};
        int capacity=24;
        boolean res=new Leetcode1094().carPooling(trip,capacity);
        System.out.println(res);
    }
}
